class Solution {
public:
    typedef long long LL;
    const LL mod=1e9+7;
    LL dp[1010][500];
    
    vector<vector<int>>res;
    vector<int>num;
    
    void dfs(int pos,int len){
         if(pos==len){
             bool flag=true;
             for(int i=0;i<num.size()-1;i++){
                 if(num[i]==num[i+1]){
                     flag=false;
                 }
             }
             if(flag){
                 res.push_back(num);
             }
             return;
         } 
         for(int i=0;i<3;i++){
             num.push_back(i);
             dfs(pos+1,len);
             num.pop_back();
         }
    }
    inline void init(int& len){
         dfs(0,len);  
    }  
    
    inline bool check(const vector<int>& a , const vector<int>& b){
        for(int i=0;i<a.size();i++){
            if(a[i]==b[i]){
                return false;
            }
        }
        return true;
    }
        
        
    int colorTheGrid(int m, int n) {
        int row=n;///变成有n行
        int col=m;///变成有m列
        
        init(m);///预处理合法的列状态
        
        // for(auto i:res){
        //     for(auto j:i){
        //         cout<<j<<" ";
        //     }
        //     cout<<endl;
        // }
        
        int siz=res.size();
        for(int j=0;j<siz;j++) dp[1][j]=1;
        
        
        for(int i=1;i<=row;i++){
            for(int j=0;j<siz;j++){
                for(int k=0;k<siz;k++){
                    if(check(res[j],res[k])){
                        dp[i][j]=(dp[i][j]%mod+dp[i-1][k]%mod)%mod;
                    }
                }
            }
        }
        
        LL ans=0;
        for(int j=0;j<siz;j++){
            ans=(ans%mod+dp[row][j]%mod)%mod;
        }
        return ans;  
    }
};